package 左哥算法.ch06二叉树;


import java.util.*;

public class SearchTree<T>{
    T val;
    SearchTree<T> parent;
    public SearchTree<T> left;
    public SearchTree<T> right;
    Comparator<? super T> comparator;

    public SearchTree(T val, Comparator<? super T> comparator) {
        this.val = val;
        this.comparator = comparator;
    }

    public SearchTree(Comparator<? super T> comparator) {
        this.comparator = comparator;
    }

    public SearchTree() {
    }

    public SearchTree(T val) {
        this.val = val;
        if (val instanceof Integer){
            this.comparator= Comparator.comparingInt(o -> (Integer) o);
        }else if(val instanceof Double){
            this.comparator=Comparator.comparingDouble(o-> (Double) o);
        }else if(val instanceof Long){
            this.comparator=Comparator.comparingLong(o-> (Long) o);
        }
    }
    /**
     * @param val：被添加的值
     * @return：返回根节点
     */
    public SearchTree<T> add(T val){
        SearchTree<T> node = new SearchTree<>(val);
        add(node);
        return this;
    }

    /**
     * 添加节点
     * @param node
     */
    protected void add(SearchTree<T> node){
        SearchTree<T> curr=this;
        SearchTree<T> parent=null;
        while (curr!=null) {
            parent=curr;
            curr=comparator.compare(curr.val,node.val)>0?curr.left:curr.right;
        }
        if (comparator.compare(parent.val,node.val)>0){
            parent.left=node;
        }else {
            parent.right=node;
        }
        node.parent=parent;
    }


    /**
     * 找到一个离Key最近的节点，这个节点的val不一定等于Key
     * @param key
     * @return
     */
    public SearchTree<T> find(T key){
        SearchTree<T> curr=this;
        SearchTree<T> res=null;
        while (curr != null) {
            res=curr;
            int compare = comparator.compare(curr.val, key);
            if (compare == 0) {
                return curr;
            }
            curr= compare>0?curr.left:curr.right;
        }
        return res;
    }


    public SearchTree<T> remove(T key){
        return remove(find(key));
    }

    /**
     * 三种情况：
     *  1.被删节点是叶子节点：直接让父节点指向空即可
     *  2.被删节点左右孩子不全：让父节点指向自己的子节点
     *  3.被删节点左右孩子双全：用左子树的最右节点替换掉当前节点
     *      替换节点的左孩子交由替换节点的父节点接管（让孩子变为父节点的右孩子）
     * 维护父引用：
     *  第一种情况无需维护
     *  第二种情况（孩子不全）：替换节点的父引用指向自己的父引用
     *  第三种情况（孩子双全）：
     *      1.当前节点的子节点：让其父引用指向替换节点
     *      2.替换节点的子节点：替换的左孩子指向替换节点的父节点
     *      3.替换节点的父引用指向当前节点的父节点
     * 实现步骤：
     *      1.找到替换节点
     *      2.维护其父引用
     *      3.替换
     * @return：返回新的根节点
     */
    protected SearchTree<T> remove(SearchTree<T> node){
        if (node==null){
            return null;
        }
        SearchTree<T> substitute=null;    //替身
        //需要维护的父引用
        SearchTree<T> subChild=null;    //替身的孩子
        if (node.left==null&&node.right==null){ //叶子节点
            if (node.parent==null) {
                return null;
            }
        }else if (node.left==null||node.right==null){   //孩子不全
            substitute=node.left!=null?node.left:node.right;
        }else {     //孩子双全
            substitute=node.left;
            while (substitute.right!=null){ //使其变为左子树最右节点
                substitute=substitute.right;
            }
            subChild=substitute.left;   //保存左孩子
            substitute.parent.right=substitute.left;
            substitute.left=node.left;
            substitute.right=node.right;
        }
        //父节点指向替换节点
        replace(node.parent,node,substitute);

        //维护父引用
        if (node.left!=null){
            node.left.parent=substitute;
        }
        if (node.right!=null){
            node.right.parent=substitute;
        }
        if (subChild!=null){
            subChild.parent=substitute.parent;
        }
        if (substitute!=null){
            substitute.parent=node.parent;
        }

        return node.parent==null?substitute:this;
    }

    /**
     * 使oldNode的父节点正确的指向newNode
     */
    public void replace(SearchTree<T> parent,SearchTree<T> oldNode, SearchTree<T> newNode){
        if (parent==null){
            return;
        }
        if (parent.left==oldNode){
            parent.left=newNode;
        }else{
            parent.right=newNode;
        }
    }

    /**
     * 左旋，并且会维护父引用
     * @return：新的头节点
     */
    public SearchTree<T> leftSpin(){
        if (this.right==null){
            return this;
        }
        SearchTree<T> newRoot = this.right;
        replace(this.parent,this,newRoot);
        this.right=newRoot.left;
        if (newRoot.left!=null) {  //维护接管的节点
            newRoot.left.parent=this;
        }
        newRoot.left=this;
        //维护父引用
        newRoot.parent=this.parent;
        this.parent=newRoot;
        return newRoot;
    }

    /**
     * 右旋，并且会维护父引用
     * @return
     */
    public SearchTree<T> rightSpin(){
        if (this.left==null){
            return this;
        }
        SearchTree<T> newRoot = this.left;
        replace(this.parent,this,newRoot);
        this.left=newRoot.right;
        if (newRoot.right!=null) {  //维护接管的节点
            newRoot.right.parent=this;
        }
        newRoot.right=this;
        //维护父引用
        newRoot.parent=this.parent;
        this.parent=newRoot;
        return newRoot;
    }


    @Override
    public String toString() {
        return val+" ";
    }

    public static void print(SearchTree root){
        int total=10;
        Map<SearchTree, Integer> map=new HashMap<>();
        Queue<SearchTree> queue=new LinkedList<>();
        List<SearchTree> list=new ArrayList<>();
        queue.add(root);
        map.put(root,1);
        int preHeight=1;
        while (!queue.isEmpty()) {
            SearchTree node = queue.poll();
            Integer currHeight = map.get(node);
            list.add(node);
            if (node.left!=null){
                queue.add(node.left);
                map.put(node.left,currHeight+1);
            }
            if (node.right!=null){
                queue.add(node.right);
                map.put(node.right,currHeight+1);
            }
            if (currHeight!=preHeight){ //不在同一层
                preHeight=currHeight;
            }
        }
        preHeight=1;
        for (SearchTree node : list) {
            int currHeight=map.get(node);
            if (preHeight!=currHeight){
                System.out.println();
                preHeight=currHeight;
            }
            int depth=total-currHeight;
            for (int i = 0; i < Math.pow(2,depth); i++) {
                System.out.printf("  ");
            }
            System.out.printf("/ "+node+"\\");
            for (int i = 0; i < Math.pow(2,depth); i++) {
                System.out.printf(" ");
            }
        }
    }
}
